//给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。 
//
// 
//
// 示例 1： 
//
// 
//输入:a = "11", b = "1"
//输出："100" 
//
// 示例 2： 
//
// 
//输入：a = "1010", b = "1011"
//输出："10101" 
//
// 
//
// 提示： 
//
// 
// 1 <= a.length, b.length <= 10⁴ 
// a 和 b 仅由字符 '0' 或 '1' 组成 
// 字符串如果不是 "0" ，就不含前导零 
// 
//
// Related Topics 位运算 数学 字符串 模拟 👍 1161 👎 0

package leetcode.editor.cn;
//java:二进制求和
public class Q0067AddBinary {
    public static void main(String[] args){
        Solution solution = new Q0067AddBinary().new Solution();
        solution.addBinary("1010", "1011");
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public String addBinary(String a, String b) {
        if (a == null || b == null || a.length() == 0 || b.length() == 0) return "";

        StringBuffer ans = new StringBuffer();
        // 去长度大的，并设置进位
        int n = Math.max(a.length(), b.length()), carry = 0;

        for (int i = 0; i < n; i++) {
            // 从后向前相加，按位求和
            carry += i < a.length() ? a.charAt(a.length() - 1 - i) - '0' : 0;
            carry += i < b.length() ? b.charAt(b.length() - 1 - i) - '0' : 0;
            ans.append((char) (carry % 2  + '0'));
            carry = carry / 2; // 进位，如果是2，进位就是1
        }

        // 最高位需要进一位
        if (carry > 0) ans.append('1');
        ans.reverse();
        return ans.toString();
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}